package leetcode_500;

import java.util.Arrays;



/**
 *@author 周杨
 *MinimumMovesToEqualArrayElementsII_462 给定一个数组 每次移动的意思就是选择一个元素增加或者减少一 问所有元素都相等的最小移动数是多少
 *describe:找出数组中位数 计算差值   AC 13%
 *2018年8月28日 上午9:49:27
 */
public class MinimumMovesToEqualArrayElementsII_462 {
	
	public static void main(String[] args) {
		MinimumMovesToEqualArrayElementsII_462  test=new MinimumMovesToEqualArrayElementsII_462();
		System.out.println(test.help(new int[] {1,2,3},0,2,1+1));
	}
	
	/**
	 * describe:完美解 线性时间找出数组中第i大的数 不必排序 。。思想相同但是AC 5%
	 * 2018年8月28日 上午10:32:51
	 */
	public int minMoves2(int[] nums) {
        int med=help(nums,0,nums.length-1,nums.length/2+1);
        int res=0;
        for(int num:nums)
        	res+=Math.abs(med-num);
        return res;
    }
	
	private int help(int[] nums,int l,int r,int i) {
		if(l==r)
			return nums[l];
		int m=partition(nums, l, r);//借助快排思想 找出一个哨兵  分割数组 左子数组全比哨兵小
		int count=m-l+1;//左边有count个数比nums[m]小
		if(i==count)
			return nums[m];
		else if(i<count)
			return help(nums, l, m-1, i);
		else
			return help(nums, m+1, r, i-count);
	}
	
	private int partition(int nums[],int l,int r) {
		int i=l-1,watch=nums[r],temp;
		for(int j=l;j<r;++j) {
			if(nums[j]<watch) {
				temp=nums[++i];
				nums[i]=nums[j];
				nums[j]=temp;
			}
		}
		nums[r]=nums[i+1];
		nums[i+1]=watch;
		return i+1;	
	}
	
	
	/**
	 * describe:求四舍五入后的中位数  思想错误
	 * 2018年8月28日 上午9:51:35
	 */
	public int minMoves2_(int[] nums) {
        double sum=0;
        for(int num:nums)
        	sum+=num;
        int med=(int) Math.round(sum/nums.length);
        int res=0;
        for(int num:nums)
        	res+=Math.abs(med-num);
        return res;
    }
	
	
	/**
	 * describe:给数组排序然后取中位数 AC 13%
	 * 2018年8月28日 上午10:15:20
	 */
	public int minMoves2__(int[] nums) {
        Arrays.sort(nums);
        int med=nums[nums.length/2];
        int res=0;
        for(int num:nums)
        	res+=Math.abs(num-med);
        return res;
    }
}
